1. Field of the Invention
This invention relates to methods, systems and computer program products for creating shape collages.
2. Background Art
The process of creating a shape collage can be complicated and time-consuming. Creating a shape collage by hand requires one to be skilled in the field of photo editing, and expend a decent amount of manual effort.
Many have recognized the value of automating collage creation, and have made computer programs that create collages automatically on the user's behalf. For example, Snapfish.com provides collage creation software on their website that allows users to build rectangular collages. The program used by Snapfish.com will take a plurality of rectangular images, along with their sizes, and arrange them to fit inside of a rectangular area. The Snapfish.com program resizes the rectangular images and arranges them in such a way that the border between images is the same size throughout the entire collage. The resulting collage is precisely rectangular in shape. Snapfish.com discloses a method and computer program for creating rectangular shape collages that consists solely of image splitting operations. In the Snapfish.com algorithm, images are added one-by one to the collage by inserting each new image next to a current image, splitting the image, and then adjusting all the other images so their shape is still a rectangle with even borders that fits within the collage area. The Snapfish.com algorithm tests multiple locations (top, bottom, left, right) and multiple images to split when adding each new image. It computes a metric based on how close the resulting rectangle's aspect ratio is to that of the collage, as well as the distribution of image sizes (images should have similar sizes, instead of one big and many small images). It then uses this metric to determine the best splitting location for each new image. The Snapfish.com algorithm and computer program only support rectangle shapes and not non-rectangular shapes. The Snapfish.com program is further unable to create collages with more than 30 images due to its inefficient approach to arranging images.
Shapecollage.com provides a computer program to automatically construct shape collages. The Shapecollage.com program employs a machine learning algorithm for iteratively adjusting image placement so that images will fit into any arbitrary shape. The algorithm tries to minimize overlap between images and minimize the amount of uncovered space inside of the collage shape. Unlike the Snapfish.com program, the Shapecollage.com program is efficient and can produce collages with thousands of images in a reasonable amount of time.
The Shapecollage.com program is somewhat undesirable because it cannot arrange images so that no images overlap and the images have even borders between them, like the Snapfish.com program. The Shapecollage.com program will start by placing images randomly in a working area, and then move all of the images inside of the desired shape. Then, it will iteratively pass over each image and adjust its placement based on nearby images. If an image can be moved to produce a more desirable covering of the shape (less overlap with other images and less empty space), then it will be moved accordingly at each step. After this algorithm is applied for several iterations, images will settle in their final places, and the Shapecollage.com program will produce a final collage image. The approach of iteratively adjusting photo placements solely using a metric based on nearby photos precludes creation of a more desirable collage that has even borders between all images and in which no images overlap.
Zumyn.com provides a computer program for creating photo mosaics. The photo mosaics created by the Zumyn.com software differ from shape collages. The mosaics are rectangular and are filled with images that are all the same size (those that are a different aspect ratio must be cropped) and have no border. Instead of arranging the photos so that their locations conform to a shape, the Zumyn.com software arranges the photos so that their colors match the color of a background image.
Picture2life.com allows users to create a collage in the shape of various countries. It appears that this site was created in 2010. The picture2life.com software creates collages in the shape of countries without any gaps or overlapping between the images. However, it will crop images so that they will all fit into rectangles of a fixed size and aspect ratio. Cropping to a fixed aspect ratio is undesirable because important parts of pictures may be cut off, especially if some are portraits and some are landscapes. It also appears that picture2life.com has a fixed number of positions (e.g. 16) for pictures in their country collages. If one has fewer than the number of slots, images will be duplicated, and if one has more, only the first N (e.g. 16) will be used. Picture2life.com does not use a dynamic method for creating shape collages, so one is limited to a fixed number of images with a fixed size and aspect ratio for each one. Most other collage generation technologies use a similar method. Having fixed positions for each of the images is undesirable because one has at least one of: gaps, overlapping, or cropping, all of which are undesirable and have a negative impact of the collage's visual appeal. Also, fixing image positions limits the number of images one can have in a collage, which is undesirable as well because people have photo albums of different sizes.
U.S. Pat. No. 7,620,267 and published U.S. patent application 2010/0164986 are related to the present invention.